package com.suanfa.matrix;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定m*n矩阵（0和1组成，只能访问0）,从[0][0]到[m-1][n-1]最短路径
 */
public class ShortMatrix {

    public static void main(String[] args) {
        int[][] grid = {{0,1,1,1,1,1,1,1}
                ,{0,1,1,0,0,0,0,0}
                ,{0,1,0,1,1,1,1,0}
                ,{0,1,0,1,1,1,1,0}
                ,{0,1,1,0,0,1,1,0}
                ,{0,1,1,1,1,0,1,0}
                ,{0,0,0,0,0,1,1,0}
                ,{1,1,1,1,1,1,1,0}};
        System.out.println(getMin(grid));
    }


    /**
     * bfs 广度优先搜索
     */
    public static int getMin(int[][] grid){
        int m = grid.length;
        int n = grid[0].length;
        if (grid[0][0] == 1 || grid[m-1][n-1] == 1){//出入口被堵塞
            return -1;
        }
        if (m==1){//只有一个
            return 1;
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0});
        int[][] pos = {{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};
        int[][] record = new int[m][n];
        record[0][0] =1;
        int step = 1;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i< size; i++){
                int[] a = queue.poll();
                int x = a[0], y = a[1];

                for(int[] p: pos){
                    int xs = x+ p[0];
                    int ys = y+ p[1];
                    if(xs <0 || ys<0 || xs>=m || ys>=n){//越界
                        continue;
                    }
                    if(record[xs][ys] == 1 || grid[xs][ys] == 1){//不能重复走已走过的路线
                        continue;
                    }

                    record[xs][ys] = 1;
                    queue.add(new int[]{xs,ys});
                }
                if(x == n-1 && y==m-1){//当前到达的点中已存在终点，则直接返回
                    return step;
                }
            }
            step++;
        }
        return -1;
    }

}
